package com.desin.modle.datastruct.myleetcode;

import com.desin.modle.datastruct.listnode.ListNode;

import java.util.*;

public class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 0,right = num;
        while(left<=right){
            int mid = left+(right-left)/2;
            long temp = (long)mid*mid;
            if(temp==num){
                return true;
            }
            if(temp<num){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return false;
    }

    public String replaceSpace(String s) {
        if(s==null||s.length()==0){
            return "";
        }
        char[] arrays = s.toCharArray();
        char flag = ' ';
        String replaceFlag = "%20";
        StringBuilder sb = new StringBuilder();
        for(char c:arrays){
            if(c==flag){
                sb.append(replaceFlag);
            }else{
                sb.append(c);
            }
        }
        return sb.toString();
    }

    public String reverseLeftWords(String s, int n) {
        if(s==null||s.length()==0){
            return "";
        }
        StringBuilder first = new StringBuilder();
        StringBuilder second = new StringBuilder();
        char[] arrays = s.toCharArray();
        for(int i=0;i<arrays.length;i++){
            if(i<=n-1){
                first.append(arrays[i]);
            }else{
                second.append(arrays[i]);
            }
        }
        second.append(first);
        return second.toString();
    }

    public int missingNumber(int[] nums) {
        int n = nums.length;
        int temp = 0;
        for(int num:nums){
            if(num==temp){
                temp++;
            }else{
                break;
            }
        }
        return temp;
    }

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix==null||matrix.length==0||matrix[0].length==0){
            return false;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        for(int i=row-1;i>=0;i--){
            for(int j=0;j<col;j++){
                if(matrix[i][j]>target){
                    break;
                }else if(matrix[i][j]<target){
                    continue;
                }else{
                    return true;
                }
            }
        }
        return false;
    }
    class TempObject {
        Character c;
        Integer num;
        public TempObject(Character c,Integer num){
            this.c=c;
            this.num=num;
        }
    }
    public char firstUniqChar(String s) {
        if(s==null||s.length()==0){
            return ' ';
        }
        Map<Character,Integer> map = new HashMap<>();
        char[] arrays = s.toCharArray();
        for(char c:arrays){
            map.put(c,map.getOrDefault(c,0)+1);
        }
        for(char c:arrays){
            if(map.get(c)==1){
                return c;
            }
        }
        return ' ';
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode soldier = new ListNode(-1);
        ListNode p = soldier;
        while(l1!=null&&l2!=null){
            if(l1.val>l2.val){
                p.next=l2;
                l2=l2.next;
            }else{
                p.next=l1;
                l1=l1.next;
            }
            p=p.next;
        }
        if(l1==null){
            p.next=l2;
        }
        if(l2==null){
            p.next=l1;
        }
        return soldier.next;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode p1 = headA;
        ListNode p2 = headB;
        while(p1!=p2){
            p1=p1==null?headB:p1.next;
            p2=p2==null?headA:p2.next;
        }
        return p1;
    }

    public int[] exchange(int[] nums) {
        if(nums==null||nums.length==0){
            return new int[0];
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for(int num:nums){
            if(num%2==0){
                queue.addLast(num);
            }else{
                queue.addFirst(num);
            }
        }
        int[] res = new int[nums.length];
        int i=0;
        for(Integer r:queue){
            res[i++]=r;
        }
        return res;
    }

    public String reverseWords(String s) {
        if(s==null||s.length()==0){
            return "";
        }
        String[] arrs = s.split(" ");
        int left = 0;
        int right = arrs.length-1;
        while(left<right){
            String temp = arrs[left];
            arrs[left]=arrs[right];
            arrs[right]=temp;
            left++;
            right--;
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<arrs.length;i++){
            if(i<arrs.length){
                sb.append(arrs[i]+" ");
            }else{
                sb.append(arrs[i]);
            }
        }
        return sb.toString();
    }

    public int movingCount(int m, int n, int k) {
        if(k==0){
            return 1;
        }
        boolean[][] marked = new boolean[m][n];
        marked[0][0]=true;
        int res = 1;
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if((i==0&&j==0)||getNum(i)+getNum(j)>k){
                    continue;
                }
                if(i-1>=0){
                    marked[i][j]|=marked[i-1][j];
                }
                if(j-1>=0){
                    marked[i][j]|=marked[i][j-1];
                }
                res+=marked[i][j]?1:0;
            }
        }
        return res;
    }
    private Integer getNum(Integer x){
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }

    public String minNumber(int[] nums) {
        if(nums==null||nums.length==0){
            return "";
        }
        quickSort(nums,0,nums.length-1);
        StringBuilder sb = new StringBuilder();
        for(int num:nums){
            sb.append(num);
        }
        return sb.toString();
    }

    private void quickSort(int[] nums, int start, int end) {
        if(start>=end){
            return;
        }
        int q = findIndex(nums,start,end);
        quickSort(nums,start,q-1);
        quickSort(nums,q+1,end);
    }

    private int findIndex(int[] nums, int start, int end) {
        int i = start;
        int point = nums[end];
        for(int j=start;j<end;j++){
            String x = String.valueOf(nums[j]);
            String y = String.valueOf(point);
            if((x+y).compareTo(y+x)<0){
                int temp = nums[i];
                nums[i]=nums[j];
                nums[j]=temp;
                i++;
            }
        }
        int temp = nums[end];
        nums[end]=nums[i];
        nums[i]=temp;
        return i;
    }

    public double myPow(double x, int n) {
        return Math.pow(x,n);
    }

    public boolean verifyPostorder(int[] postorder) {
        return verifyPostorderHelper(postorder,0,postorder.length-1);
    }

    private boolean verifyPostorderHelper(int[] postorder, int left, int right) {
        if(left>=right){
            return true;
        }
        int p = left;
        while (postorder[p]<postorder[right]) p++;
        int m = p;
        while (postorder[p]>postorder[right]) p++;
        return p==right&&verifyPostorderHelper(postorder,left,m-1)&&verifyPostorderHelper(postorder,m,right-1);
    }

    public int cuttingRope(int n) {
        if(n<=3){
            return n-1;
        }
        int[] dp = new int[n+1];
        for(int i=3;i<=n;i++){
            for(int j=1;j<i;j++){
                dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }

    public int[] quickSort(int[] nums){
        quickSortHelper(nums,0,nums.length-1);
        return nums;
    }

    private void quickSortHelper(int[] nums, int begin, int end) {
        if(begin>=end){
            return;
        }
        int q = findNum(nums,begin,end);
        quickSortHelper(nums,begin,q-1);
        quickSortHelper(nums,q+1,end);
    }

    private int findNum(int[] nums, int begin, int end) {
        int point = nums[end];
        int i = begin;
        for(int j=begin;j<end;j++){
            if(nums[j]<point){
                int temp = nums[j];
                nums[j]=nums[i];
                nums[i]=temp;
                i++;
            }
        }
        int temp = nums[end];
        nums[end]=nums[i];
        nums[i]=temp;
        return i;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] ints = solution.hebingArray(new int[]{1,2,3},new int[]{3,4,5});
        System.out.print(ints);
    }

    public int singleNum(int[] nums){
        int ans = 0;
        for(int num:nums){
            ans^=num;
        }
        return ans;
    }

    public int[] hebingArray(int[] nums1,int[] nums2){
        if(nums1==null||nums1.length==0){
            return nums2;
        }
        if(nums2==null||nums2.length==0){
            return nums1;
        }
        int a = nums1.length;
        int b=nums2.length;
        List<Integer> list = new ArrayList<>();
        int aIndex = 0;
        int bIndex = 0;
        while (aIndex<a&&bIndex<b){
            if(nums1[aIndex]<nums2[bIndex]){
                list.add(nums1[aIndex]);
                aIndex++;
            }else{
                list.add(nums2[bIndex]);
                bIndex++;
            }
        }
        if(aIndex<a){
            for(int i=aIndex;i<a;i++){
                list.add(nums1[i]);
            }
        }
        if(bIndex<b){
            for(int i=bIndex;i<b;i++){
                list.add(nums2[i]);
            }
        }
        int[] res = new int[list.size()];
        int i =0;
        for(int num:list){
            res[i++]=num;
        }
        return res;
    }

    public ListNode fanzhuan2(ListNode head,int left,int right){
        ListNode soldier = new ListNode(-1);
        soldier.next = head;
        ListNode p = soldier;
        for(int i=1;i<left;i++){
            p=p.next;
        }
        ListNode cur = p.next;
        for(int i=left;i<right;i++){
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next=p.next;
            p.next=temp;
        }
        return soldier.next;
    }

    public ListNode hebingK(ListNode[] lists){
        if(lists==null||lists.length==0){
            return null;
        }
        PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2)->o1.val-o2.val);
        for(ListNode node:lists){
            if(node!=null) {
                queue.offer(node);
            }
        }
        ListNode soldier = new ListNode(-1);
        ListNode p = soldier;
        while(!queue.isEmpty()){
            ListNode temp = queue.poll();
            p.next = temp;
            p=p.next;
            if(temp.next!=null){
                queue.offer(temp.next);
            }
        }
        return soldier.next;
    }

    public int zhongshu(int[] nums){
        Map<Integer,Integer> map = new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        int res = nums[0];
        int ans=1;
        for(Map.Entry<Integer,Integer> a:map.entrySet()){
            if(a.getValue()>ans){
                res = a.getKey();
                ans = a.getValue();
            }
        }
        return res;
    }

    public int[] kNum(int[] nums,int k){
        Map<Integer,Integer> map = new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        PriorityQueue<Map.Entry<Integer,Integer>> queue = new PriorityQueue<>((o1,o2)->o2.getValue()-o2.getValue());
        for(Map.Entry<Integer,Integer> a:map.entrySet()){
            queue.offer(a);
        }
        int[] res = new int[k];
        for(int i=0;i<k;i++){
            res[i]=queue.poll().getKey();
        }
        return res;
    }
}
